// 约瑟夫环问题
// 解法： 可以通过链表或者数组进行模拟
// 也可以使用递推公式，递归或者动态规划求解

// 动态规划解法：
// 第一轮游戏结束后，淘汰了 (m - 1) % n 号下标元素, 从 m % n 号元素开始，编号为 0, 继续第二轮游戏
// 然而最终剩下的元素 x 是确定的，游戏还没开始就已经注定了，第二轮重新编完号也不能改变结果，改变的只是元素的下标
// 随便选一个元素 x，下标的变化是：(x - m) % n
// 因此就可以借助下标的关系递推剩下元素的下标：
// dp[i] 表示 i 个元素最后剩下的下标, dp[i] = (dp[i - 1] + m) % i

public class Solution {
    public int LastRemaining_Solution (int n, int m) {
        // write code here
        int a = 0;

        for(int i = 2; i <= n; i++){
            a = (a + m) % i;
        }

        return a;
    }

    public  int LastRemaining_Solution1 (int n, int m) {
        // write code here
        // write code here
        boolean[] check = new boolean[5000];
        int index = -1;

        for(int i = 1 ; i <= n - 1; i++){
            for(int j = 0; j < m; j++){
                index++;
                while(check[index % n] != false){
                    index++;
                }
            }
            check[index % n] = true;
        }

        for(int i = 0; i < n; i++){
            if(check[i] == false){
                return i;
            }
        }
        return -1;
    }

}
